//
// Description: 10. 正则表达式匹配
// Created by Loading on 2022/5/23.
//

#include <bits/stdc++.h>

using namespace std;

bool isMatch(string s, string p) {
    int m = s.size();
    int n = p.size();

    auto match = [&](int i, int j) {
        // 除空串外任意串与空串匹配，均失败
        if (i == 0) {
            return false;
        }
        // '.' 可以表示任意单个字符，均成功
        if (p[j - 1] == '.') {
            return true;
        }

        // 对应位置字符相同，匹配成功
        return s[i - 1] == p[j - 1];
    };

    // dp[i][j] 表示 s 中的前 i 个字符与 p 中的前 j 个字符是否匹配
    bool dp[m + 1][n + 1];
    memset(dp, false, sizeof dp);
    dp[0][0] = true;

    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] != '*') {
                // 当前不是'*'，i 与 j 匹配成功时 dp[i][j] = dp[i - 1][j - 1]，否则为false
                dp[i][j] = match(i, j) && dp[i - 1][j - 1];
            } else {
                // 当前是'*'，i 与 j - 1 匹配成功时，dp[i][j] = dp[i - 1][j] | dp[i][j - 2]，否则为 dp[i][j - 2]（放弃字符+'*'组合）
                dp[i][j] = match(i, j - 1) ? dp[i - 1][j] | dp[i][j - 2] : dp[i][j - 2];
            }
        }
    }

    return dp[m][n];
}

int main() {
    string s = "aaa";
    string p = "aa";
    auto res = isMatch(s, p);
    cout << res << endl;

    return 0;
}